//<p>给你链表的头结点&nbsp;<code>head</code>&nbsp;，请将其按 <strong>升序</strong> 排列并返回 <strong>排序后的链表</strong> 。</p>
//
//<ul>
//</ul>
//
//<p>&nbsp;</p>
//
//<p><strong>示例 1：</strong></p>
//<img alt="" src="https://assets.leetcode.com/uploads/2020/09/14/sort_list_1.jpg" style="width: 450px;" />
//<pre>
//<b>输入：</b>head = [4,2,1,3]
//<b>输出：</b>[1,2,3,4]
//</pre>
//
//<p><strong>示例 2：</strong></p>
//<img alt="" src="https://assets.leetcode.com/uploads/2020/09/14/sort_list_2.jpg" style="width: 550px;" />
//<pre>
//<b>输入：</b>head = [-1,5,3,4,0]
//<b>输出：</b>[-1,0,3,4,5]
//</pre>
//
//<p><strong>示例 3：</strong></p>
//
//<pre>
//<b>输入：</b>head = []
//<b>输出：</b>[]
//</pre>
//
//<p>&nbsp;</p>
//
//<p><b>提示：</b></p>
//
//<ul>
//	<li>链表中节点的数目在范围&nbsp;<code>[0, 5 * 10<sup>4</sup>]</code>&nbsp;内</li>
//	<li><code>-10<sup>5</sup>&nbsp;&lt;= Node.val &lt;= 10<sup>5</sup></code></li>
//</ul>
//
//<p>&nbsp;</p>
//
//<p><b>进阶：</b>你可以在&nbsp;<code>O(n&nbsp;log&nbsp;n)</code> 时间复杂度和常数级空间复杂度下，对链表进行排序吗？</p>
//<div><div>Related Topics</div><div><li>链表</li><li>双指针</li><li>分治</li><li>排序</li><li>归并排序</li></div></div><br><div><li>👍 1661</li><li>👎 0</li></div>

package com.rising.leetcode.editor.cn;

import com.rising.leetcode.editor.cn.doc.object.ListNode;

/**
 * 排序链表
 * @author DY Rising
 * @date 2022-06-27 20:25:42
 */
public class P148_SortList{
    public static void main(String[] args) {
        //测试代码
        Solution solution = new P148_SortList().new Solution();
        ListNode head = new ListNode(2);
        ListNode next = new ListNode(1);
        head.next = next;
        ListNode listNode = solution.sortList(head);
        while (listNode != null) {
            System.out.print(listNode.val + " ");
            listNode = listNode.next;
        }
    }
	 
//力扣代码
//leetcode submit region begin(Prohibit modification and deletion)
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode sortList(ListNode head) {
        /*if (head == null || head.next == null) return head;
        ListNode current = head.next.next;
        ListNode second = head.next;
        ListNode first = head;
        head.next = null; second.next = null;
        ListNode mergeNode = mergeTwoLists(first, second);
        while (current != null) {
            mergeNode = mergeTwoLists(mergeNode, current);
            current = current.next;
        }
        return mergeNode;*/
        return sortList(head, null);
    }

    public ListNode sortList(ListNode head, ListNode tail) {
        if (head == null) {
            return head;
        }
        if (head.next == tail) {
            head.next = null;
            return head;
        }
        ListNode slow = head, fast = head;
        while (fast != tail) {
            slow = slow.next;
            fast = fast.next;
            if (fast != tail) {
                fast = fast.next;
            }
        }
        ListNode mid = slow;
        ListNode list1 = sortList(head, mid);
        ListNode list2 = sortList(mid, tail);
        ListNode sorted = mergeTwoLists(list1, list2);
        return sorted;
    }

    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        ListNode node = null;
        ListNode head = new ListNode();
        node = head;
        while (list1 != null || list2 != null) {
            if (list1 == null) {
                node.next = list2;
                node = node.next;
                list2 = list2.next;
                continue;
            }
            if (list2 == null) {
                node.next = list1;
                node = node.next;
                list1 = list1.next;
                continue;
            }
            if (list1.val <= list2.val) {
                node.next = list1;
                node = node.next;
                list1 = list1.next;
            } else {
                node.next = list2;
                node = node.next;
                list2 = list2.next;
            }
            continue;
        }
        return head.next;
    }

}
//leetcode submit region end(Prohibit modification and deletion)

}
